This invention relates to high-speed, broadband communication networks and, more particularly, to a self routing crossbar switch suitable for communicating data packets in an ATM switch.
High-speed, broad-band communication networks include systems for routing data packets from input sources to output sources. U.S. Pat. Nos. 5,305,311 and 5,327,420 disclose such switching networks. The basic architecture of such prior art systems include an Asynchronous Transfer Mode (ATM) Local Area Network (LAN) using a VLSI-based "Batcher/banyan" switching fabric of the type which has been developed by AT&T/Bellcore. Batcher/banyan switching technology will scale to switches larger than 256 ports, and link rates exceeding 1 gigabit/sec and these switches can be interconnected to form a larger hierarchical network for supporting larger user communities.
An advantage of such Batcher/banyan switch fabrics is that they are "self routing". That is, data packets are routed through the switching fabric on the basis of local decisions only, there is no global "chokepoint". For each stage in the network, routing can be determined with only the information contained in the data packets entering that stage of the switch; that is, with locally available information. Such networks are also advantageous when they are "non-blocking". In any switching cycle, the network is capable of generating an arbitrary permutation, or a partial permutation, of its inputs. More simply stated, a non-blocking switching fabric is able to generate all possible one to one input/output mappings in a single switching cycle.
Ideally such a switching fabric provides parallelism whereby a single N port Batcher sorting network can feed some number k (typically two or three) banyan routing switches that are connected so that as many as k-cells can be routed to the same number of output ports during the same cell switching cycle without losing any of the data packets. However, in order to overcome the problem that occurs when more than one data packet is found to be destined to the same output port during the single switch cycle, a "reservation ring" is provided for fairly adjudicating the contention among such conflicting data packets, while permitting at most k of them to be presented to the switch in any cycle. Reservation rings resolve output contentions among conflicting data packets, while implementing "fair" access to the output ports of the switching fabric.
The first bits of a data packet contain the address to which the packet should be routed. Such "first bits" are typically referred to as the "header", and identify the path through the switching fabric, the source and destination of which are input and output ports. For a particular switch, the input and output ports associated with a given virtual circuit are defined at connection establishment. A virtual circuit is thus the ultimate source and ultimate destination, and all the intermediate switches therebetween defining the path through the fabric. Accordingly, the contents of the header are defined by the virtual circuit as the path through the particular switching fabric. Switching fabric such as Batcher/banyans allow many possible paths between any given input and output pair and present a problem which is sought to be overcome by the present invention. The problem is that it is very difficult to diagnose failures in a Batcher/banyan switch fabric due to the multiple possible paths. A failure is difficult to replicate because of the many possible paths.
The present invention contemplates a new and improved switching fabric to replace the Batcher/banyan network of prior art systems, provide easier diagnosis of failures in the fabric than in the Batcher/banyan network, is simple in design, economical to manufacture and which provides better scaling properties than a Batcher/banyan for the size of the switching fabrics that the subject invention is applicable to be implemented as in a commercial embodiment.